package com.leetcode;

import com.leetcode.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

import static com.leetcode.util.BinaryTreeUtil.createTree;
import static com.leetcode.util.BinaryTreeUtil.printTree;

/**
 * 100. 相同的树
 * 广度优先搜索
 *
 * @author fy
 * @date 2022-04-17 17:50
 */
public class Solution100_1 {

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        q1.offer(p);
        q2.offer(q);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();
            if (node1.val != node2.val) {
                return false;
            }
            TreeNode left1 = node1.left;
            TreeNode right1 = node1.right;

            TreeNode left2 = node2.left;
            TreeNode right2 = node2.right;

            if (left1 == null && left2 != null) {
                return false;
            }
            if (left1 != null && left2 == null) {
                return false;
            }
            if (right1 == null && right2 != null) {
                return false;
            }
            if (right1 != null && right2 == null) {
                return false;
            }

            if (left1 != null) {
                q1.offer(left1);
                q2.offer(left2);
            }
            if (right1 != null) {
                q1.offer(right1);
                q2.offer(right2);
            }
        }
        return q1.isEmpty() && q2.isEmpty();
    }

    public static void main(String[] args) {
        Integer[] pNums = new Integer[]{1, 2, 1};
        TreeNode p = createTree(pNums);
        printTree(p);

        Integer[] qNums = new Integer[]{1, 2, 1};
        TreeNode q = createTree(qNums);
        printTree(q);

        boolean res = new Solution100_1().isSameTree(p, q);
        System.out.println(res);
    }

}
